package PersonStu.siqi;

import javafx.scene.web.WebHistory;

/**
 * @Author by KoVaVo
 * @Date 2023-01-08 16:43
 * @Desc:
 * 约瑟夫环问题
 *
 */
public class code02_josephusKill {

    public static class Node {
        public int value;
        public Node next;

        public Node(int data) {
            this.value = data;
        }
    }

    //给一个单循环链表，数到m就杀掉，返回最后一个没有被杀掉的节点，自己组成环
    public static Node josephusKill(Node head,int m){
        if(head == null || head.next == head || m < 1){
            return head;
        }
        Node cur = head.next;
        int size = 1;
        //看下一个有多少个节点
        while (cur != head){
            size++;
            cur = cur.next;
        }
        //返回长度为 i 的 最后存活的是哪个编号
        int live = getLive(size,m);
        while (--live != 0) {
            head = head.next;
        }
        head.next = head;
        return head;
    }

    //长度为 i 的 最后存活的那个位置的编号
    private static int getLive(int i, int m) {
        if(i == 1){
            return 1;
        }
        int live = getLive(i-1,m);
        return ( live + m - 1) % i + 1;
    }

    public static void printCircularList(Node head) {
        if (head == null) {
            return;
        }
        System.out.print("Circular List: " + head.value + " ");
        Node cur = head.next;
        while (cur != head) {
            System.out.print(cur.value + " ");
            cur = cur.next;
        }
        System.out.println("-> " + head.value);
    }



    public static void main(String[] args) {
        Node head2 = new Node(1);
        head2.next = new Node(2);
        head2.next.next = new Node(3);
        head2.next.next.next = new Node(4);
        head2.next.next.next.next = new Node(5);
        head2.next.next.next.next.next = head2;
        printCircularList(head2);
        head2 = josephusKill(head2, 3);
        printCircularList(head2);
    }
}
